package com.wjcxf.solution;

import com.wjcxf.utils.CalcUtil;

import java.util.*;

public class BullsAndCowsSolution {
    public static int[] numbers = {0,1,2,3,4,5,6,7,8,9};
    //可能的结果集
    public ArrayList<BANode> resultCollection = new ArrayList<>(5040);
    public ArrayList<BANode> resultCollection2 = new ArrayList<>(5040);
    //提示历史记录
    public ArrayList<ResultHistory> resultHistories = new ArrayList<>();
    public int[] answerList = new int[4];
    public int answerNumber;
    //回溯法相关数据结构
//    public Deque<Integer> deque = new ArrayDeque<>();
//    public static Set<Integer> used = new HashSet<>();

    public void init(){
        resultCollection.clear();
        resultCollection2.clear();
        resultHistories.clear();
//        deque.clear();
//        used.clear();
        //back_track(deque,0);
        //不用回溯了，直接for
        for(int i=123;i<9999;i++){
            int g = i%10;
            int s = (i/10)%10;
            int b = (i/100)%10;
            int q = (i/1000)%10;
            if(!(g == s) && !(g == b) && !(g == q) && !(s == b) && !(b==q) && !(s == q)){
                resultCollection.add(new BANode(i));
                resultCollection2.add(new BANode(i));
            }
        }
    }
//    private void back_track(Deque<Integer> deque,int depth){
//        if(depth == 4){
//            Iterator<Integer> iterator = deque.iterator();
//            int num=0;
//            int i=0;
//
//            while(iterator.hasNext()){
//                int t = iterator.next();
//                num += t*CalcUtil.pow(10,i);
//                ++i;
//            }
//            resultCollection.add(new BANode(num));
//            resultCollection2.add(new BANode(num));
//        }
//        for(int i=0;i<numbers.length;i++){
//            if(!used.contains(numbers[i])){
//                used.add(numbers[i]);
//                deque.addLast(numbers[i]);
//                back_track(deque,depth+1);
//                used.remove(numbers[i]);
//                deque.removeLast();
//            }
//        }
//    }
    public BullsAndCowsSolution(){
        //用回溯法找到所有结果集

        init();

    }
    public int calcGuessNumber(){
        //根据历史记录筛选结果集
        int total = resultCollection.size();
        if(resultHistories.size()==0){
            //对于第一次猜测，信息熵的增量都是一样的，所以随机返回一个就行
//            return resultCollection.get(new Random().nextInt()).num;
            return 1234;
        }

        if(total >=1){

            //遍历当前结果集，计算信息熵增量，选取信息熵增量最大的结果

            int infoEntropyIndex = 0;

            double infoEntropy = 0.0;
            for (int i = 0; i < resultCollection.size(); i++) {
                BANode node = resultCollection.get(i);
                LinkedHashMap<String,Integer> map = new LinkedHashMap<>();
                int sum = 0;
                for (int j = 123; j < resultCollection.size(); j++) {
                    BANode t_node = resultCollection.get(j);
                    for(int k = 0;k<CalcUtil.abList.length;k++) {
                        int a = CalcUtil.abList[k][0];
                        int b = CalcUtil.abList[k][1];
                        boolean flag = node.checkAnswer(t_node.arr, CalcUtil.abList[k][0], CalcUtil.abList[k][1]);
                        if (flag) {
                            if (map.containsKey(node.num+","+a+","+b)) {
                                map.put(node.num+","+a+","+b, map.get(node.num+","+a+","+b) + 1);
                            } else {
                                map.put(node.num+","+a+","+b, 1);
                            }
                            sum ++;
                        }
                    }
                }
                //根据hashmap 计算信息熵
                double tmpInformationEntropy = getInformationEntropy(map,sum);
//                System.out.println("sum:"+sum);
//                System.out.println("info:"+tmpInformationEntropy);
                if(infoEntropy<=tmpInformationEntropy){
                    infoEntropy = tmpInformationEntropy;
                    infoEntropyIndex = i;
                }
            }
            return resultCollection.get(infoEntropyIndex).num;
        }
        return 0;
    }
    public double getInformationEntropy(LinkedHashMap map,int total){
        double result = 0.0;
        Iterator<Map.Entry<String,Integer>> iterator = map.entrySet().iterator();
        while(iterator.hasNext()){
            Map.Entry<String,Integer> entry = iterator.next();
            int value = entry.getValue();
            result += ((double)value/(double)total)*(CalcUtil.log((double)value/(double)total,2.0));
//            System.out.println(value);
        }
        return -result;
    }
    //自动验证并生成结果
    public void autoSolution(){
        int[] data=new int[12];
        Arrays.fill(data,0);
        for(int i=0;i<resultCollection2.size();i++){
            //1.设置答案
            BANode node =resultCollection2.get(i);
            for(int k = 0;k<node.arr.length;k++){
                answerList[k] = node.arr[k];
            }
            answerNumber = node.num;
            int calcAnswer = this.solution1();
            if(calcAnswer == answerNumber){
                data[resultHistories.size()] ++;
            }
            if(i%100==0)
                System.out.println(i+"/5040");

            init();
        }
        for(int i=0;i<data.length;i++){
            System.out.println(data[i]);
        }
    }


    public void solution(){
        Scanner scanner = new Scanner(System.in);
        while(true){
            int guessNumber = calcGuessNumber();
            System.out.println("推荐数字:"+guessNumber);
            String inputStr = scanner.next();
            String[] inputArr = inputStr.split(",");
            if(inputArr.length != 2){
                if("exit".equals(inputStr.toLowerCase()) || "bye".equals(inputStr.toLowerCase())){
                    System.out.println("GoodBye");
                    System.exit(0);
                }
                System.out.println("格式错误,输入格式应为A,B");
                continue;
            }
            int a = Integer.parseInt(inputArr[0]);
            int b = Integer.parseInt(inputArr[1]);
            int[] guessNumArr = new int[]{guessNumber%10,(guessNumber/10)%10,(guessNumber/100)%10,(guessNumber/1000)%10};
            ResultHistory resultHistory = new ResultHistory(guessNumArr,a,b);
            resultHistories.add(resultHistory);
            //根据历史记录筛掉不符合条件的记录
            Iterator iterator = resultCollection.iterator();
            while(iterator.hasNext()){
                BANode node = (BANode) iterator.next();
                if(!node.checkAnswer(guessNumArr,a,b)){
                    iterator.remove();
                }else {
                    //计算每种结果所能获取的信息量，然后排序
                    //[0,0][1,0][1,1][0,1]
                }
            }
            System.out.println("当前结果集size="+resultCollection.size());
            if(resultCollection.size() <=0){
                break;
            }
        }

    }

    //简单策略
    public int solution1(){

        while(true){
            int guessNumber = calcGuessNumber();
            BANode baNode = new BANode(answerNumber);
            int[] guessNumArr = new int[]{guessNumber%10,(guessNumber/10)%10,(guessNumber/100)%10,(guessNumber/1000)%10};
            int a = baNode.getACount(guessNumArr);
            int b = baNode.getBCount(guessNumArr);

            ResultHistory resultHistory = new ResultHistory(guessNumArr,a,b);
            resultHistories.add(resultHistory);
            //根据历史记录筛掉不符合条件的记录
            Iterator iterator = resultCollection.iterator();
            while(iterator.hasNext()){
                BANode node = (BANode) iterator.next();
                if(!node.checkAnswer(guessNumArr,a,b)){
                    iterator.remove();
                }
            }
            //System.out.println("当前结果集size="+resultCollection.size());
            if(resultCollection.size() ==1){
                break;
            }
        }
        return resultCollection.get(0).num;

    }
    public void test(){
        BANode node = new BANode(1234);
        int num = 1234;
        int[] arr = new int[]{num%10,(num/10)%10,(num/100)%10,(num/1000)%10};
        System.out.println(node.checkAnswer(arr,4,0));
    }
    class BANode{
        public int a;
        public int b;

        public int num;
        public int[] arr;
        public BANode(int num){
            this.num =num;
            this.arr = new int[]{num%10,(num/10)%10,(num/100)%10,(num/1000)%10};
        }
        public int getBCount(int[] guessArr){
            int result = 0;
            for(int i = 0;i<guessArr.length;i++){
                for(int j = 0;j<this.arr.length;j++){
                    if(i!=j&& guessArr[i] == this.arr[j]){
                        result++;
                    }
                }
            }
            return result;
        }
        public int getACount(int[] guessArr){
            int result = 0;
            for(int i = 0;i<guessArr.length;i++){
                if(this.arr[i] == guessArr[i]){
                    result++;
                }
            }
            return result;
        }
        public boolean checkAnswer(int[] guessArr,int a,int b){
            //假设这个数就是正确答案，计算ab，再根据猜测反馈的ab值判断是否需要筛除
            int calcA = this.getACount(guessArr);
            int calcB = this.getBCount(guessArr);
            return calcA == a && calcB == b;
        }
    }
    class ResultHistory{
        public int arr[];
        public int a,b;
        public ResultHistory(int[] arr,int a,int b){
            this.arr = arr;
            this.a = a;
            this.b = b;
        }
    }
}
